package ACM_Brush;

import java.util.Scanner;

public class Solution072 {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            String word1 = in.nextLine();
            String word2 = in.nextLine();
            System.out.println();
            System.out.println(new solution_072().minDistance(word1, word2));
        }
    }
}

class solution_072 {
    public int minDistance(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        int[][] dp = new int[length1 + 1][length2 + 1]; // dp[i][j] 表示 s1[0~i] 和 s2[0~j] 的最小编辑距离
        // 初始化
        for (int i = 0; i < length1 + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < length2 + 1; j++) {
            dp[0][j] = j;
        }
        // 状态转移
        for (int i = 1; i < length1 + 1; i++) {
            for (int j = 1; j < length2 + 1; j++) {
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);
                dp[i][j] = c1 == c2 ? Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1])
                        : Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
        return dp[length1][length2];
    }
}